import Heap.TestHeap;

import java.util.*;

class Student {
}

class IntCmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class Test {


    public static void main(String[] args) {
        int[] array={27,15,19,18,28,34,65,49,25,37};
        TestHeap testHeap=new TestHeap();
        testHeap.init(array);
        testHeap.createHeap();

        testHeap.heapSort();
    }



//    最小k个数
    public static int[] smallestK1(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i=0;i<arr.length;i++) {
            minHeap.offer(arr[i]);
        }
        int[] tmp=new int[k];
        for(int i=0;i<k;i++) {
            int val=minHeap.poll();
            tmp[i]=val;
        }
        return tmp;
    }

    public static int[] smallestK2(int[] arr, int k) {
        int[] tmp=new int[k];
        if(k==0) return tmp;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new IntCmp());
        //1. 把前k个元素放入k中
        for(int i=0;i<k;i++) {
            maxHeap.offer(arr[i]);
        }
        //2. 遍历剩下的n-k个元素
        for(int i=k;i<arr.length;i++) {
            int val=maxHeap.peek();
            if(val>arr[i]) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        for(int i=0;i<k;i++) {
            tmp[i]=maxHeap.poll();
        }
        return tmp;
    }

    public static void main4(String[] args) {
        int[] array={27,15,19,18};
        int[] ret=smallestK2(array,3);
        System.out.println(Arrays.toString(ret));
    }


    public static void main3(String[] args) {
        ArrayList list=new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);

        //优先队列
        PriorityQueue<Integer> pq=new PriorityQueue<>(new  IntCmp());
        pq.offer(12);
        pq.offer(5);
        pq.offer(57);
        System.out.println(pq.peek());//优先队列默认是小根堆

        /*

        PriorityQueue<Student> pq2=new PriorityQueue<>();
        pq2.offer(null);
        pq2.offer(new Student());*/
    }

    public static void main2(String[] args) {
        int[] array={27,15,19,18,28,34,65,49,25,37};
        TestHeap testHeap=new TestHeap();
        testHeap.init(array);
        testHeap.createHeap();

//        testHeap.offer(80);

        testHeap.poll();
    }

    public static void main1(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextLine()) {
            String str=sc.nextLine();
            TreeNode root=binaryTree.createTree(str);

            System.out.println("======层序遍历=====");
            binaryTree.levelOrder(root);

            System.out.println("====测试一棵树是否是完全二叉树====");
            System.out.println(binaryTree.isCompleteTree(root));
        }
    }

}
